package everyday;

/**
 * @author zhangmin
 * @create 2022-05-04 11:22
 * 给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
 * 请你找出符合题意的 最短 子数组，并输出它的长度。
 *
 * 思路：
 * 1、将原数组排序后与原数组比较找到最长前缀和后缀
 * 2、双指针+线性扫描：通过双指针先找到左右两边满足单调的位置i，j，则在（i,j）之间是无序的，然后对中间这部分进行遍历，
 * 找到其中的最小值，然后将这个最小值插入的[0,i]之间合适的位置，这个位置就是需要排序的起始位置
 * 同理找到最大值，将最大值插入的[j,n)之间合适的位置。那这个位置就是需要排序的结束位置
 */
public class findUnsortedSubarray581 {
    public int findUnsortedSubarray(int[] nums) {
        int n=nums.length;
        int i=0,j=n-1;
        int MAX=100005,MIN=-100005;
        while (i<j&&nums[i]<=nums[i+1]) i++;
        while (i<j&&nums[j]>=nums[j-1]) j--;
        int l=i,r=j;
        int min=nums[i],max=nums[j];
        //开始遍历中间的部分，一边找最大最小，一边移动i的位置
        for (int k = l; k <= r; k++) {
            if (nums[k]<min){
                //最小值更新
                while (i>=0&&nums[i]>nums[k]){
                    i--;
                }
                min=i>=0?nums[i] :MIN;
            }
            if (nums[k]>max){
                while (j<n&&nums[j]<nums[k]){
                    j++;
                }
                max=j<n?nums[j]:MAX;
            }
        }
        return j==i?0:(j-1)-(i+1)+1;
    }
}
